package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20240908;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode3283 {
    // 相邻相关排列型状压DP
    // 记忆化搜索
    private static final int[][] DIRS={{2,1},{1,2},{-1,2},{-2,1},{-2,1},{-2,-1},{1,-2},{2,-1}};
    public int maxMoves(int kx,int ky,int[][] positions){
        int n=positions.length;
        // 计算马到兵的步数，等价于计算兵到其余格子的步数
        int[][][] dis=new int[n][50][50];
        for(int i=0;i<n;i++){
            int[][] d=dis[i];
            for(int j=0;j<50;j++){
                Arrays.fill(d[j],-1);
            }
            int px=positions[i][0];
            int py=positions[i][1];
            d[px][py]=0;
            List<int[]> q= new ArrayList<>();
            q.add(new int[]{px,py});
            for(int step=1;!q.isEmpty();step++){
                List<int[]> tmp=q;
                q=new ArrayList<>();
                for(int[] p : tmp){
                    for(int[] dir : DIRS){
                        int x=p[0]+dir[0];
                        int y=p[1]+dir[1];
                        if(0<=x && x<50 && 0<=y && y<50 && d[x][y]<0){
                            d[x][y]=step;
                            q.add(new int[]{x,y});
                        }
                    }
                }
            }
        }
        int[][] memo=new int[n+1][1<<n];
        for(int[] row : memo){
            Arrays.fill(row,-1);// -1表示没有计算过
        }
        return dfs(n,(1<<n)-1,kx,ky,positions,dis,memo);
    }

    private int dfs(int i,int mask,int kx,int ky,int[][] positions,int[][][] dis,int[][] memo){
        if(mask==0){
            return 0;
        }
        if(memo[i][mask]!=-1){// 之前计算过
            return memo[i][mask];
        }
        int n=positions.length;
        int x=i<n ? positions[i][0] : kx;
        int y=i<n ? positions[i][1] : ky;

        int res=0;
        int u=(1<<n)-1;
        if(Integer.bitCount(u^mask)%2==0){// Alice操作
            for(int j=0;j<n;j++){
                if((mask>>j & 1)>0){
                    res=Math.max(res,dfs(j,mask^(1<<j),kx,ky,positions,dis,memo)+dis[j][x][y]);
                }
            }
        }else{
            res=Integer.MAX_VALUE;
            for(int j=0;j<n;j++){
                if((mask>>j & 1)>0){
                    res=Math.min(res,dfs(j,mask^(1<<j),kx,ky,positions,dis,memo)+dis[j][x][y]);
                }
            }
        }
        return memo[i][mask]=res;// 记忆化
    }
}
